Public-key cryptographic techniques are widely used for encryption and authentication of electronic documents. Such techniques use a mathematically-related key pair: a secret private key and a freely-distributed public key. A sender encrypts a message using the recipient's public key. The recipient then decrypts the message using the corresponding private key. In a well-designed scheme, it is computationally infeasible to reconstruct the private key from the public key or to otherwise decrypt the message without having possession of the private key.
Commonly-used public-key cryptographic techniques, such as the Rivest Shamir Adleman (RSA) algorithm, rely on numerical computations over large finite fields. To ensure security against cryptanalysis, these techniques require the use of large keys and complex computations, which are costly, in terms of memory and computing power, to store and compute. These demands can be problematic in application environments such as smart cards, in which computing resources are limited.
Various alternative public-key signature schemes have been developed in order to reduce the resource burden associated with cryptographic operations. Some schemes of this sort are based on the Merkle-Hellman knapsack cryptosystem, which was first described by Merkle and Hellman in “Hiding Information and Signatures in Trapdoor Knapsacks,” IEEE Transactions on Information Theory 24:5, pages 525-530 (1978). Unfortunately, knapsack-based schemes, including those based on more secure iterated-knapsack approaches that were developed subsequently, have been found to be vulnerable to attacks based on lattice reduction and the Diophantine approximation. Such vulnerabilities are reviewed, for example, by Brickell in “Breaking Iterated Knapsacks,” Advances in Cryptology—Crypto '84, pages 342-358 (Springer-Verlag, 1985).